package io.github.maojian.dynamicprogramming;

/**
 * 轰炸敌人
 * 给你一个二维的网格图，网格图中的每一个格子里要么是一堵墙 'W' ，要么是一个敌人 'E' ，要么是一个空位 '0' （数字 0 ），返回你用一个炸弹最多能杀死敌人的数量。
 *
 * 由于墙体足够坚硬，炸弹的威慑力没有办法穿越墙体，所以炸弹只能把所在位置同一行和同一列所有没被墙挡住的敌人给炸死。
 * 注意：你只能把炸弹放在一个空的格子里
 */
public class Q361 {
    public int maxKilledEnemies(char[][] grid) {
        int rows = grid.length;
        if (rows == 0) return 0;
        int cols = grid[0].length;
        if (cols == 0) return 0;
        int ans = 0;
        int[][] dp = new int[rows][cols];
        int pre = 0;    // 敌人的个数
        // 遍历每一行
        for (int i = 0; i < rows; i++) {
            pre = 0;
            // 从左到右
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 'W') {
                    pre = 0;   // 当前格子是墙，前一个格子不能在这边接触到任何敌人
                } else if (grid[i][j] == 'E') {
                    pre++;    // 当前格子就是敌人，告诉前一个能接触的敌人加一
                } else { // '0'
                    dp[i][j] += pre;   // 当前格子是空格，它能接触到的敌人就是 pre
                }
            }
            pre = 0;
            // 从右到左
            for (int j = cols - 1; j >= 0; j--) {
                if (grid[i][j] == 'W') {
                    pre = 0;    // 当前格子是墙，往右不能接触到任何敌人
                } else if (grid[i][j] == 'E') {
                    pre++;
                } else {
                    dp[i][j] += pre;
                }
            }
        }
        // 遍历每一列
        for (int j = 0; j < cols; j++) {
            pre = 0;
            // 从上到下
            for (int i = 0; i < rows; i++) {
                if (grid[i][j] == 'W') {
                    pre = 0;
                } else if (grid[i][j] == 'E') {
                    pre++;
                } else {
                    dp[i][j] += pre;
                }
            }
            pre = 0;
            // 从下到上
            for (int i = rows - 1; i >= 0; i--) {
                if (grid[i][j] == 'W') {
                    pre = 0;
                } else if (grid[i][j] == 'E') {
                    pre++;
                } else {
                    dp[i][j] += pre;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '0') {
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
}
